/**
 * FileName: TestTwoColorabilityForAdjacenyMatrix.c
 * ----------------------------------------------------------------------------------------------------
 * 测试邻接矩阵表示的图是否为二分图，或者是否具有二着色性，或者其是否不包含任何长度为奇数的环？
 * - 基于DFS递归树对图的边进行的分类
 */

#include <stdio.h>
#include <stdlib.h>

//边相关
typedef struct {
    int v;
    int w;
}
Edge;

//图相关
typedef struct graph *Graph;
struct graph {
    int V;
    int E;
    int** adj;
    int* color;
};

static int cnt;
static int* pre;

//辅助函数声明
int** MATRIXinit(int, int, int);
Edge EDGE(int, int);
void GRAPHshow(Graph);
void dfsR(Graph, Edge);
int dfsRcolor(Graph, int, int);

//图操作声明
Graph GRAPHinit(int);
void GRAPHinsertE(Graph, Edge);
void GRAPHremoveE(Graph, Edge);
int GRAPHedges(Edge [], Graph);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);
int GRAPHtwocolor(Graph);

//辅助函数实现
/**
 * Program 17.4 Adjacency-matrix allocation and initialization
 * -------------------------------------------------------------------------------------------------------------
 * This program uses the standard C array-of-arrays representation for the two-dimensional adjacency matrix (see Section 3.7).
 * It allocates `r` rows with `c` integers each, then initializes all entries to the value `val`.
 *
 * The call `MATRIXinit(V, V, 0)` in Program 17.3 takes time proportional to $V^2$ to create a matrix that
 * represents a V-vertex graph with no edges.
 *
 * For small $V$, the cost of $V$ calls to `malloc` might predominate.
 */
int** MATRIXinit(int r, int c, int val) {
    int i;
    int j;
    int** t = malloc(r * sizeof(int*));
    for (i = 0; i < r; i++) {
        t[i] = malloc(c * sizeof(int));
    }
    for (i = 0; i < r; i++) {
        for (j = 0; j < c; j++) {
            t[i][j] = val;
        }
    }
    return t;
}

Edge EDGE(int v, int w) {
    Edge edge;
    edge.v = v;
    edge.w = w;
    return edge;
}

void GRAPHshow(Graph G) {
    int i;
    int j;
    printf("%d vertices, %d edges\n", G->V, G->E);

    //邻接列表
    for (i = 0; i < G->V; i++) {
        printf("%2d:", i);
        for (j = 0; j < G->V; j++) {
            if (i < j && G->adj[i][j] == 1) {
                printf(" %2d", j);
            }
        }
        printf("\n");
    }
    // //邻接矩阵
    // for (i = 0; i < G->V; i++) {
    //     printf("%2d:", i);
    //     for (j = 0; j < G->V; j++) {
    //         printf(" %2d", G->adj[i][j]);
    //     }
    //     printf("\n");
    // }
}

/**
 * Program 18.1 Depth-first search (adjacency-matrix)
 * --------------------------------------------------------------------------------------------------------------------
 * This code is intended for use with a generic graph-search ADT function that
 * - initializes a counter `cnt` to 0 and all of the entries in the vertex-indexed array `pre` to -1,
 * - then calls search once for each connected component (see Program 18.3),
 * assuming that the call `search(G, EDGE(v, v))` marks all vertices in the same connected component as `v`
 * (by setting their `pre` entries to be nonnegative).
 *
 * Here, we implement `search` with a recursive function `dfsR` that visits all the vertices connected to `e.w`
 * by scanning through its row in the adjacency matrix and
 * calling itself for each edge that leads to an unmarked vertex.
 * --------------------------------------------------------------------------------------------------------------------
 * 递归版dfs
 * @param G
 * @param edge
 */
void dfsR(Graph G, Edge e) {
    int t;
    int w = e.w;
    pre[w] = cnt++;
    for (t = 0; t < G->V; t++) {
        if (G->adj[w][t] != 0) {
            if (pre[t] == -1) {
                dfsR(G, EDGE(w, t));
            }
        }
    }

}
/**
 * Program 18.6 Two-colorability
 * ---------------------------------------------------------------------------------------------------------------------
 * This DFS function assigns the values 0 or 1 to the vertex-indexed array `G->color` and
 * indicates in the return value whether or not it was able to do the assignment such that,
 * for each graph edge `v-w`, `G->color[v]` and `G->color[w]` are different.
 * ---------------------------------------------------------------------------------------------------------------------
 * Two-colorability, bipartiteness, odd cycle
 * - Is there a way to assign one of two colors to each vertex of a graph such that
 *   no edge connects two vertices of the same color?
 * - Is a given graph bipartite (see Section 17.1)?
 * - Does a given graph have a cycle of odd length?
 */
int dfsRcolor(Graph G, int v, int c) {
    int t;
    G->color[v] = 1-c;
    for (t = 0; t < G->V; t++) {

        if (G->adj[v][t] != 0) {
            if (G->color[t] == -1) {
                //tree link: t是v的孩子节点
                if (!dfsRcolor(G, t, 1-c)) {
                    return 0;
                }
            }else if (G->color[t] == c) {
                //parent link: t是v的父节点
            }else if (G->color[t] != c) {
                //back edge: t是v的祖先，且t不是v的父节点
                return 0;
            }
        }
    }
    return 1;
}


//图操作函数实现
Graph GRAPHinit(int V) {
    Graph G = malloc(sizeof(*G));
    G->V = V;
    G->E = 0;
    G->adj = MATRIXinit(V, V, 0);
    return G;
}

void GRAPHinsertE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    if (G->adj[v][w] == 0) {
        G->E++;
    }
    G->adj[v][w] = 1;
    G->adj[w][v] = 1;
}

void GRAPHremoveE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    if (G->adj[v][w] == 1) {
        G->E--;
    }
    G->adj[v][w] = 0;
    G->adj[w][v] = 0;
}
int GRAPHedges(Edge a[], Graph G) {
    int v;
    int w;
    int E = 0;
    for (v = 0; v < G->V; v++) {
        for (w = v+1; w < G->V; w++) {
            if (G->adj[v][w] == 1) {
                a[E++] = EDGE(v, w);
            }
        }
    }
    return E;
}
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);

int GRAPHtwocolor(Graph G) {
    int v;
    G->color = malloc(G->V * sizeof(int));
    for (v = 0; v < G->V; v++) {
        G->color[v] = -1;
    }
    for (v = 0; v < G->V; v++) {
        if (G->color[v] == -1) {
            if (!dfsRcolor(G, v, 0)) {
                return 0;
            }
        }
    }
    return 1;
}

//测试函数声明
void test_twocolor();
void test_twocolor2();

int main(int argc, char *argv[]) {
    test_twocolor();
    test_twocolor2();
    return 0;
}

//测试函数实现
//图18.5
void test_twocolor() {
    int V = 8;
    Graph G = GRAPHinit(V);
    Edge edge1 = EDGE(0, 2);
    Edge edge2 = EDGE(0, 5);
    Edge edge3 = EDGE(0, 7);
    Edge edge4 = EDGE(2, 6);
    Edge edge5 = EDGE(5, 3);
    Edge edge6 = EDGE(5, 4);
    Edge edge7 = EDGE(7, 1);
    Edge edge8 = EDGE(7, 4);
    Edge edge9 = EDGE(3, 4);
    Edge edge10 = EDGE(4, 6);

    GRAPHinsertE(G, edge1);
    GRAPHinsertE(G, edge2);
    GRAPHinsertE(G, edge3);
    GRAPHinsertE(G, edge4);
    GRAPHinsertE(G, edge5);
    GRAPHinsertE(G, edge6);
    GRAPHinsertE(G, edge7);
    GRAPHinsertE(G, edge8);
    GRAPHinsertE(G, edge9);
    GRAPHinsertE(G, edge10);

    int canTwoColor = GRAPHtwocolor(G);
    if (canTwoColor) {
        printf("Twocolor\n");
    }else {
        printf("No twocolor\n");
    }
}
//图17.5
void test_twocolor2() {
    int V = 13;
    Graph G = GRAPHinit(V);
    Edge edge1 = EDGE(0, 1);
    Edge edge2 = EDGE(0, 3);
    Edge edge3 = EDGE(0, 5);
    Edge edge4 = EDGE(1, 2);
    Edge edge5 = EDGE(3, 4);
    Edge edge6 = EDGE(5, 4);
    Edge edge7 = EDGE(2, 9);
    Edge edge8 = EDGE(4, 11);
    Edge edge9 = EDGE(9, 6);
    Edge edge10 = EDGE(9, 8);
    Edge edge11 = EDGE(9, 10);
    Edge edge12 = EDGE(9, 12);
    Edge edge13 = EDGE(11, 12);
    Edge edge14 = EDGE(6, 7);
    Edge edge15 = EDGE(7, 8);



    GRAPHinsertE(G, edge1);
    GRAPHinsertE(G, edge2);
    GRAPHinsertE(G, edge3);
    GRAPHinsertE(G, edge4);
    GRAPHinsertE(G, edge5);
    GRAPHinsertE(G, edge6);
    GRAPHinsertE(G, edge7);
    GRAPHinsertE(G, edge8);
    GRAPHinsertE(G, edge9);
    GRAPHinsertE(G, edge10);
    GRAPHinsertE(G, edge11);
    GRAPHinsertE(G, edge12);
    GRAPHinsertE(G, edge13);
    GRAPHinsertE(G, edge14);
    GRAPHinsertE(G, edge15);

    int canTwoColor = GRAPHtwocolor(G);
    if (canTwoColor) {
        printf("Twocolor\n");
    }else {
        printf("No twocolor\n");
    }

    // int i;
    // for (i = 0; i < G->V; i++) {
    //     printf("%d ", G->color[i]);
    // }
    // printf("\n");
}
